package searchtree

/**
  * 排序二叉树
  */
object SearchBinaryTreeDemo {
    def main(args: Array[String]): Unit = {
        val arr: Array[Int] = Array(1,2,3,4,5,6,7,8)
        val tree: SearchBinaryTree[Int] = initSearchTree(arr)
        tree.infixForeach(x=> print(x + "->"))
        println(tree.search(1))
        tree.delete(2)
        tree.infixForeach(x=> print(x + "->"))

    }

    /**
      * 初始化排序二叉树
      * @param arr
      * @return
      */
    def initSearchTree(arr:Array[Int]) : SearchBinaryTree[Int]={
        val tree: SearchBinaryTree[Int] = new SearchBinaryTree[Int]
        arr.foreach(tree.add)
        tree
    }
}
class SearchBinaryTree[T: Ordering]{
    var root :TreeNode[T] = _


    def search(value:T):TreeNode[T]={
        if(root == null) null
        else {
            root.search(value)     //节点调用search方法,这value哪来的？？？？
        }

    }


    def delete(v:T) :Boolean ={  //传进来的是某个节点的值
        if (root == null) false
        else if(root.value == v) {  //判断式root节点的情况时，又细分下面3中情况
            // 4种情况 左右都为空  左右子树都存在 左右子树有一个不为空   删除其他节点
            if(root.left == null && root.right == null) root = null //直接删除跟节点

            else if(root.left != null && root.right != null){  //左右子树都存在
                root.value = root.right.deleteMin()


            }else{ // 左右子树有一个不为空, 让根节点指向这个这个不为空的节点
                root = if(root.left != null) root.left else root.right
            }
            true

        }else {  //非根节点情况
            //删除其他子节点
            root.delete(v)
        }
    }


    //类的函数，类调用，节点的函数，节点来掉用
    def add (value:T):Boolean={
        if(root == null) root =new TreeNode[T](value)
        else root.add(value)

        true
    }

    //中序遍历
    def infixForeach(op: T => Unit): Unit = {
        if (root != null) {
            if (root.left != null) root.left.infixForeach(op)
            op(root.value)
            if (root.right != null) root.right.infixForeach(op)
        }
    }
}

class TreeNode[T:Ordering](var value:T){
    var left :TreeNode[T] = _
    var right : TreeNode[T] = _
    var p : TreeNode[T] =_

    /**
      * 删除最小的节点 并返回这个节点
      * @return
      */
    def deleteMin():T ={
        var minNode :TreeNode[T] =this
        while(minNode.left != null){  //循环结束找到最小的节点
            minNode = minNode.left
        }
        //用来删除节点 ，并返回该节点
        minNode.delete(minNode.value)
        minNode.value
    }


    def delete(v:T):Boolean={
        val ord:Ordering[T] = implicitly[Ordering[T]]

        //三种情况：等于  小于  大于
        if(ord.equiv(v,value)){    // =

            // 先判断当前节点是它父节点的左节点还是右节点
            var isLeft :Boolean = true
            if(p != null && p.right != null && ord.equiv(p.right.value,value) ){  //判断这个节点是右节点
                isLeft = false
            }

            //当前节点是否为叶子节点
            if(left == null && right == null){  // 删除右叶子节点
                if(isLeft) p.left = null
                else p.right == null

            } else if(left != null && right != null){ //左孩子，右孩子都在
                value = right.deleteMin()

            } else { //有一个不为空
                //找非空的子节点
                val notNullNode = if(left != null) left else right
                notNullNode.p = p    //当前节点的父节点 变成非空子节点的父节点
                if(isLeft) p.left = notNullNode  //重新设置左节点的父节点
                else p.right = notNullNode

            }

             true
        } else if(ord.lt(v,value)){  // <=
            if(left == null) false
            else left.delete(v)

        } else {                    // >=
            if(right == null) false
            else right.delete(v)

        }

        true
    }


    /**
      *给当前节点添加元素
      *  val arr: Array[Int] = Array(8, 4, 9, 10, 1, 6, 7, 12)
      * @param v
      * @return
      */
    def add(v:T):Boolean={
        val ord :Ordering[T] = implicitly[Ordering[T]]

        //如果小于当前节点
        if(ord.lteq(v,value)){  //lteq(v,value)  v 小于等于 value
            if(left == null){
                left = new TreeNode[T](v)
                left.p = this  // 指定父节点是自己  this为 value的节点

            }else{
                left.add(v)   //开始循环、调用，最终调用的还是上边
            }
        }else{
            if(right == null){
                right = new TreeNode[T](v)
                right.p =  this  // 指定父节点是自己  this为 value的节点

            }else{
                right.add(v)
            }
        }
        true
    }


    def search(v:T):TreeNode[T]={
       // println(v)
        val ord:Ordering[T] = implicitly[Ordering[T]]
        if(ord.equiv(v,value)){ //这 value 是哪来的
            this
        }else if(ord.lt(v,value)){
            if(left == null) null
            else left.search(v)

        }else {
            if (right == null) null
            else right.search(v)
        }
    }




    //中序
    def infixForeach(op :T => Unit) :Unit ={  //op 为遍历的节点  不存在左右节点，直接输出value
        if(left != null) left.infixForeach(op)  //左边存在
        op(value)
        if(right != null) right.infixForeach(op)  //右边存在

    }

}

